package com.liuzhilong.infrastructure.framework.algorithms.algorithms.doublepointer;
/**
 *
 * <h1>双指针思想</h1>
 *
 * <p>双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的</p>
 *
 * <p>
 *     <h2>
 *         对撞指针
 *     </h2>
 *     <p>
 *         指在数组中，将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历
 *     </p>
 *     <h2>
 *         快慢指针
 *     </h2>
 *     <p>
 *         快慢指针也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如fast每次增长两个，slow每次增长一个
 *     </p>
 * </p>
 * @author 21012273
 */
public class DoublePointer {
    /**
     * <h2>最大乘积</h2>
     * <p>
     *     给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
     * </p>
     * <p>
     *     核心思想： 使用碰撞指针。每次都移动最小的指针。如果舍弃大的，乘积不会大于之前的乘积。存在着相关算法证明。
     * </p>
     * <link>https://leetcode-cn.com/problems/container-with-most-water</link>
     * @param array
     * @return
     */
    public static final int maxWaterCapacity(int[] array) {

        int left = 0;
        int right = array.length - 1, diff = array.length - 1;
        int max = 0;
        while (diff >= 1) {
            int min = array[left] > array[right] ? array[right] : array[left];
            int plus = diff * min;
            max = max > plus ? max : plus;
            if(array[left] > array[right]){
                right--;
            }else {
                left++;
            }
            diff--;

        }

        return max;
    }

    public static void main(String[] args) {
        int[] a = new int[]{1, 1} ;
        System.out.println(maxWaterCapacity(a));

    }
}
